1. Field of the Invention
The present invention relates to a multiobjective optimization apparatus, a multiobjective optimization method, and a multiobjective optimization program which optimizes the parameters of a target to be optimized.
2. Description of the Background Art
Conventionally, problem classes referred to as multiobjective optimization problems exist. As an example, a multiobjective optimization problem with two objective functions arises when one wishes to minimize the cost of a product while maximizing its performance. In this case, the cost and the performance are the two objective functions. In general, a trade-off relationship exists whereby reducing the cost degrades the performance while improving the performance increases the cost. Accordingly, the solution to such a multiobjective optimization problem cannot be a single solution.
FIG. 36 is a diagram showing the application of the multiobjective optimization problem to the optimization of an engine. In the application of the multiobjective optimization problem to the optimization of fuel consumption and torque of an engine, the fuel consumption and torque are the two objective functions f1, f2. In this case, the values of the objective functions f1, f2 are optimized by adjusting parameters such as the amount of injected fuel, ignition timing, etc.
A solution A is superior to a solution B in fuel consumption, while being inferior to the solution B in torque. Since in this manner, the fuel consumption and engine torque have a trade-off relationship, a plurality of optimal solutions can be found. A user can select a solution from the plurality of optimal solutions that is suited to a particular purpose. For example, for an engine used in an automatic motorcycle suited for sport operation, the solution A is selected, and for an engine used in an automatic motorcycle suited for long touring, the solution B is selected.
The multiobjective optimization problem, in general, is defined as a problem of minimizing the values of M objective functions with respect to N parameters within the range of constraints for each parameter. Maximization of objective function values is converted to a problem of minimizing the objective function values by applying a minus sign to the objective functions.
Such a multiobjective optimization problem typically does not have a single optimal solution but has a population of optimal solutions which are defined as the concept referred to as Pareto-optimal solutions. Note that a Pareto-optimal solution is one in which an improvement in one objective function value requires a degradation of another, which is defined as follows (refer to Document 1, for example):
Definition 1
Given two solutions x1, x2εF for p objective functions fk (k=1, ·. . . , p), x1 is said to dominate x2 if fk(x1)<fk(x2) (∀k=1, . . . , p) ^ fk(x1)<fk(x2) (∃k=1, . . . , p), where F is a population of solutions.
Definition 2
A solution x0 is an optimal solution if x0 dominates all the other solutions xεF.
Definition 3
A solution x0 is a Pareto-optimal solution (or non-inferior solution) if there does not exist any solutions xεF that dominate x0.
Determining a population of Pareto-optimal solutions means to determine a population of optimal solutions for a tradeoff relationship between objective functions.
FIG. 37 is a diagram for use in illustrating Pareto-optimal solutions, showing an example of two objective functions f1, f2. The value of the objective function f1 for the solution a, f1 (a), is smaller than the value of the objective function f2 for the solution b, f1 (b), while the value of the objective function f2 for the solution a, f2(a), is smaller than the value of the objective function f2 for the solution b, f2(b). The solution a therefore dominates the solution b.
Similarly, the solution a dominates the solutions c, d. There does not exist any solutions that dominate the solution a. Also, solutions that dominate the solutions e, f do not exist. This makes the solutions a, e, f the Pareto-optimal solutions.
Note that the solution g is a weak Pareto-optimal solution. A weak Pareto-optimal solution is one that is not dominated by Pareto-optimal solutions with respect to only one objective function. Such a weak Pareto-optimal solution is not a reasonable one, and does not essentially have to be determined.
A number of solutions have been proposed for multiobjective optimization problems, among which are Multiobjective Evolutionary Algorithms (MOEAs) that have recently attracted attention. The most important feature of this method is using a multiple point search in an evolutionary algorithm to determine a population of Pareto-optimal solutions at a time. The population of Pareto-optimal solutions obtained is used, e.g., for decision making in determining a solution among them that is suited to a particular purpose, or for making determinations from the shape of the population of Pareto-optimal solutions (i.e., Pareto-boundary).
Numerous studies are being conducted on the application of genetic algorithms (GAs) as evolutionary algorithms to multiobjective optimization problems. A genetic algorithm is a computing technique that imitates the adaptive evolution in biology. In genetic algorithms, candidate solutions are referred to as individuals, objective functions are referred to as fitness functions, and fitness function values are referred to as fitnesses.
The genetic algorithm is an algorithm suggested by J. Holland, and involves obtaining hints from the processes observed in natural evolution such as selection, crossover, or mutation of chromosomes. Taking design variables as genes, a population of individuals at the initial design is randomly generated, and the fitnesses of each individual are evaluated. A parent is selected such that an individual of better fitnesses is more likely to be selected as the parent. Then, offspring is produced by means of crossover (shuffling of genes) and mutation (random alteration of genes). Generation is iterated by further evaluations, selections, crossovers, and mutations to search for optimal solutions.
More specifically, Fonseca et al. proposed MOGA (Multiple Objective Genetic Algorithm: e.g., refer to Document 1), Deb et al. proposed NSGA-II (Non-Dominated Sorting Genetic Algorithm-II: e.g., refer to Document 2), and Zitzler et al. proposed SPEA2 (Strength Pareto Evolutionary Algorithm 2: e.g., refer to Document 3), to cite examples. NSGA-II and SPEA2, in particular, are known as very useful multiobjective evolutionary algorithms.
Actual applications of multiobjective evolutionary algorithms include problems of determining the wing shape for a supersonic transport, optimization of parameters of a vehicle or engine, etc.
In order to optimize fitness functions having uncertainty, MFEGA (Memory-based Fitness Estimation Genetic Algorithm) was also proposed by Sano, Kita, et al., which allows estimation of true fitnesses using search history (e.g., refer to Document 4). The MEFGA includes storing the sampled data of fitnesses for the previously obtained individuals as a search history, and estimating true fitnesses by reference to the search history. Regarding problems with uncertainty, the MFEGA is reported to have a better search performance than the usual genetic algorithms and methods which require sampling the fitnesses of an identical individual a number of times.
However, the genetic algorithms suggested in Document 1, Document 2 and Document 3 are all applied to a simulation which always results in the same solution, as in the case of a benchmark problem or an ideal model which does not contain probability factors. None of the cases has reported the application of the above-mentioned genetic algorithms to a problem with individuals having noisy fitnesses, as in a real system or a simulation containing probability factors, i.e., a problem having uncertainty. This may be explained by the following two reasons.
For one thing, because a target to be optimized contains noise, the fitnesses of individuals obtained from the optimization target vary for each evaluation, which prevents a satisfactory evolution. That is, individuals that should originally provide good fitnesses are eliminated because the fitnesses are degraded by noise. Meanwhile, individuals that should provide poor fitnesses survive because the fitnesses are improved by noise. Such phenomena prevent normal evolution of the individuals.
For another, the shape of a resulting population of Pareto-optimal solutions is unclear. That is, because of the noisy fitnesses obtained, a Pareto-boundary is not formed when the fitnesses are plotted on the plane of fitness function space, for example, in a two-objective optimization problem. This makes the conventional genetic algorithms difficult for use in decision making or making determinations.
Examples of real systems and simulations containing probability factors that require multiobjective optimization include the optimization of signal switching rules using a traffic volume simulator and the optimization of control parameters of a motor. The purpose of the optimization of signal switching rules is to prevent a traffic jam on two highways by successfully switching the signals at an intersection of and near these highways. The purpose of the optimization of control parameters of a motor is to achieve both the increased responsiveness in the motor and decreased overshoot.
However, for the traffic volume simulator, the velocity and number of passing vehicles are randomly given, and for the motor, measurement errors may be made by sensors, and therefore, computation of fitnesses using the identical individuals (i.e., the rules and the control parameters) results in fitnesses that vary each time. This causes the above-described two problems.
Such problems with uncertainty present serious difficulties not only in multiobjective optimization, but also in single objective optimization. In evolutionary algorithms, several methods for statistically coping with noise are proposed. The most common one involves sampling individuals a number of times, by which with the number of sampling times being n, the noise variance can be decreased to n−0.5. The method, however, increases the evaluation time to a factor of n, which makes it undesirable for use in a time-consuming real system or large-scale simulation.
The MFEGA suggested in Document 4 exhibits good search performance for single objective optimization problems, but fails to provide sufficient studies on applications for multiobjective optimization problems.
(Document 1) C. M. Fonseca, P. J. Fleming: Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization; Proceedings of the 5th International Conference on Genetic Algorithms, pp. 416-423 (1993).
(Document 2) K. Deb, S. Agrawal, A. Pratab, and T. Meyarivan: A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II, KanGAL Report 20001, Indian Institute of Technology, Kanpur, India (2000).
(Document 3) E. Zitzler, M. Laumanns, L. Thiele: SPEA2: Improving the Performance of the Strength Pareto Evolutionary Algorithm, Technical Report 103, Computer Engineering and Communication Networks Lab (TIK), Swiss Federal Institute of Technology (ETH) Zurich (2001).
(Document 4) Sano, Kita: Optimization of Noisy Fitness Functions by Means of Genetic Algorithms Using History of Search With Test of Estimation; The Transactions of the Institute of Electrical Engineers of Japan, Vol. 122-C, No. 6, pp. 1001-1008 (2002).
(Document 5) K. Ikeda, H. Kita, and S. Kobayashi: Failure of Pareto-Based MOEAs, Does Non-Dominated Really Mean Near to Optimal?; Congress on Evolutionary Computation, pp. 957-962 (2001).
(Document 6) M. D. Berg, et al.: Computational. Geometry: Algorithms and Applications, Springer-Verlag (1997).
(Document 7) Hiroshi Imai, Keiko Imai: Computer Science, Jouhou Sugaku Kouza 12 (Lecture on Information Mathematics No. 12), Kyoritsu Publishing (1994).
(Document 8) E. Zitzler, K. Deb, L. Thiele: Comparison of Multiobjective Evolutionary Algorithms: Empirical Results, Evolutionary Computation 8(2), pp. 173-195 (2000).